package com.algorithms.sorts.advances;

import com.algorithms.sorts.Sort;

/**
 * ShellSort<br>
 * Complexity O(N*log^2(N))<br><br>
 * 
 * algorithms:<br>
 * - this will first find the gap (interval), for example g = g * 3 + 1<br>
 * - notice that g * 3 + 1 < length (of array)<br>
 * - sort the arrays which their indices are distanced by the gap g using <b>InsertionSort</b><br>
 * - loop with the arrays which indices are distanced by the (g - 1) / 3<br>
 * - loop until the gap g = 1
 * 
 * @author minhld
 *
 */
public class ShellSort extends Sort{
	
	public ShellSort(int[] dataArray, int dataLength){
		super(dataArray, dataLength);
		this.sortName = "ShellSort";
	}
	
	@Override
	public int[] sort(){
		// find max gap
		int gap = 1;
		while (gap < this.length){
			gap = 3 * gap + 1;
		}
		
		int marker = 0;
		int step = 0, innerStep = 0;
		while (gap > 0){
			step = gap;

			// do the insertion sort on the gap array
			while (step < this.length){
				marker = this.data[step];
				innerStep = step - gap;
				
				while (innerStep >= 0 && marker < this.data[innerStep]){
					this.data[innerStep + gap] = this.data[innerStep];
					innerStep -= gap;
					
					this.numOfCopy++;
					this.numOfProcess++;
				}
				
				if (innerStep + gap >= 0){
					this.data[innerStep + gap] = marker;
					
					this.numOfCopy++;
				}
				
				step++;
				this.numOfProcess++;
			}
			
			// reduce the gap
			gap = (gap - 1)/3;
		}
		
		return this.data;
	}
	
	
}
